The present invention relates generally to the field of Computer-Aided Design (CAD) systems and methods, and in particular, to CAD systems and methods for digital circuit verification and testing.
Computer-aided design of digital circuits and other complex digital systems is widely prevalent. The requirements of the circuit or system are defined in an abstract model of the circuit or system. The abstract model is then successfully transformed into a number of intermediate stages. These intermediate stages often include a register transfer level model which represents a block structure behavioral design, and a structural model which is a logic level description of the system. Eventually, a transistor net list and consequently the physical layout of the circuit or system are derived.
The design of the circuit or system therefore proceeds from the general requirements level to the lower detailed level of the physical design interposed between are a number of intermediate levels. Each successive level of the design is tested or verified to insure that the circuit or system continues to meet the design specifications.
If the design verification step fails, a diagnosis is typically invoked to determine possible causes for the failure. During the design phase, prior to actual physical implementation of the circuit the diagnosis is generally termed error diagnosis. After physical implementation of the circuit, the diagnosis is generally termed fault diagnosis. Such diagnosis, whether error diagnosis or fault diagnosis, provides valuable feedback to designers and process engineers. The diagnosis can identify potential error sites in the design or circuit. This is helpful because a particular design or circuit may contain numerous elements and the verification stage may provide little or no information as to which elements may require adjustment to achieve proper behavior. Providing a limited set of candidates where correction could be performed accordingly may significantly decrease the time and difficulty of correcting design or circuit operation.
Conventionally, error diagnosis has primarily focused on diagnosing single errors. Furthermore, error diagnosis methods are often limited as to the types of errors which may be located. Therefore, these error diagnosis methods are limited in scope. In addition, extending these error diagnosis methods to diagnosis multiple errors generally results in erroneous error locations or requires excessive amounts of time to perform error location.
As previously alluded, fault diagnosis is the process of locating failures in the digital circuit at the fabrication stage of the design flow. Fault diagnosis examines a specific part of a digital circuit to determine causes of failure in the circuit. Manufacturing errors or fabrication defects, such as shorts caused by dust particles introduced into the silicon of an integrated circuit, improper soldering, or incorrect wiring, are examples of faults.
Current methods of fault diagnosis have similar limitations as methods of error diagnosis. These methods identify a single fault or error, but fail to accurately identify multiple faults or errors. The ability of the diagnosis to handle multiple errors or faults, however, has become increasingly important as digital circuits have become more complicated.
The present invention provides a method and system for determining potential locations of errors or faults in a circuit design. The errors or faults results in the output behavior of the circuit design not matching the output behavior of a circuit specification when a predetermined test vector is applied to both the circuit design and the circuit specification. In one embodiment, a list of candidate nodes is created, the list comprised of nodes in the circuit design. A test vector is applied to the circuit design and the candidate nodes are set to an X value. The X value is a logic value of a 0, 1, X three value logic system. The output behavior of the circuit design upon application of the test vector, with the candidate nodes set to X, is determined. An error probability is assigned to the list of candidate nodes depending on whether the output behavior of the circuit design changes as a result of setting the candidate nodes to X. The error probability is increased if the output behavior changes and the error probability decreases if the output behavior does not change.
A list of further candidate nodes is also created, and the test vector is applied to the circuit design, and the further candidate nodes are set to X. The output behavior of the circuit design is again determined and an error probability is assigned to the further candidate of nodes. The process is repeated for lists of other candidate nodes and other test vectors, with the output behavior of the circuit design determined and error probabilities assigned. In various embodiments of the present invention, output behavior comparison is between various combinations of a circuit design, a physical circuit, and a circuit specification.
In some embodiments, the candidate nodes are determined using error models, including a region-based model, a topological based model, a cut based model, and a register transfer level based model. Levels of confidence in the models to identify the errors or faults in the circuit are used in the assignment of error probabilities. In conjunction with error or fault models, the method and system guarantees in instances that the errors.or faults are entirely at a set of nodes when the model exactly covers the errors or faults.
In one embodiment of the present invention provides that the candidate nodes have inputs and outputs, with at least some of the inputs being determined by the test vector and at least some of the primary outputs having values dependent on the values of at least some of the outputs. The required values of the outputs to obtain output behavior of the circuit design matching output behavior of the circuit specification is determined. A relationship between the at least some of the inputs and the at least some of the outputs is determined, with the relationship resulting in the at least some of the outputs having the required values upon application of the test vector.
A further test vector is applied to the circuit design and further required values of the outputs to obtain output behavior of the circuit design matching output behavior of the circuit specification is determined. A further relationship between the at least some of the inputs and the at least some of the outputs is determined, with the further relationship resulting in the at least some of the outputs having the further required values upon application of the further test vector. An error probability is assigned to the list of candidate nodes. The error probability depends on the consistency of the relationship between the at least some of the inputs and the at least some of the outputs upon application of the test vector and the further test vector.
The process is repeated for other test vectors and lists of other candidate nodes with the relationship between the at least some of the inputs and the at least some of the outputs upon application of the test vectors determined and the error probability assigned. Furthermore, the use of symbolic logic variables and binary decision diagrams are used to determine required values for the at least some of the outputs.
These and other features of the present invention will be more readily appreciated as the same becomes better understood by reference to the following detailed description when considered in connection with the accompanying drawings.